<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Reasons for Combining Solvers
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial122.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial124.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc240">17.2</A>&nbsp;&nbsp;Reasons for Combining Solvers</H2>
The <TT>ic</TT> solver library implements two kinds of constraints
<UL CLASS="itemize"><LI CLASS="li-itemize">
finite domain constraints
<LI CLASS="li-itemize">interval constraints
</UL>
Each constraint is handled separately and individually, and the only
communication between them is via the bounds on their shared
variables. <BR>
<BR>
The benefits of the <TT>ic</TT> solvers are
<OL CLASS="enumerate" type=1><LI CLASS="li-enumerate">
the repeated tightening of guaranteed upper and lower bounds on the
variables
<LI CLASS="li-enumerate">the application of tailored algorithms to standard subproblems
(encapsulated as global constraints)
<LI CLASS="li-enumerate">the implementation of a very wide class of constraints
</OL>
The <TT>eplex</TT> solver library implements two kinds of constraints
<UL CLASS="itemize"><LI CLASS="li-itemize">
linear numeric constraints
<LI CLASS="li-itemize">integrality constraints
</UL>
The linear constraints are handled by a very powerful solver that
enforces <EM>global</EM> consistency on all the constraints.
The integrality constraints are handled via a built-in search
mechanism.<BR>
<BR>
The benefits of the <TT>eplex</TT> solvers are
<OL CLASS="enumerate" type=1><LI CLASS="li-enumerate">
the enforcement of global consistency for linear constraints
<LI CLASS="li-enumerate">the production of an optimal solution satisfying the linear constraints
</OL>
For some years researchers have sought to characterise the classes of
problems for which the different solvers are best suited. 
Problems involving only linear constraints are very well handled by
<TT>eplex</TT>.
Problems involving disjunctions of constraints are often best
handled by <TT>ic</TT>.
Often set covering problems are best handled by <TT>eplex</TT> and
scheduling problems by <TT>ic</TT>.
However in general there is no method to recognise for a new problem
which solver is best.<BR>
<BR>
Luckily in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> there is no need to choose a specific solver for each
problem, since it is possible to apply both solvers. Moreover the
solvers communicate with each other, thus further speeding up constraint
solving.
The <TT>ic</TT> solver communicates new tightened bounds to the 
<TT>eplex</TT> solver. These tightened bounds have typically been deduced
from non-linear constraints and thus the linear solver benefits from
information which would not otherwise have been available to it.
On the other hand the <TT>eplex</TT> solver often detects inconsistencies
which would not have been detected by the <TT>ic</TT> solvers. Moreover
it returns a bound on the optimisation function which can be used by
the <TT>ic</TT> constraints. 
Finally the optimal solution returned by <TT>eplex</TT> to the
&#8220;relaxed&#8221; problem
comprising just the linear constraints, can be used as a
search heuristic that can focus the <TT>ic</TT> solver on the most
promising parts of the search space.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
There are two main reasons for combining <TT>eplex</TT> and <TT>ic</TT> in
a hybrid algorithm
<UL CLASS="itemize"><LI CLASS="li-itemize">
<TT>ic</TT> handles a wider class of constraints than <TT>eplex</TT>
<LI CLASS="li-itemize">The solvers extract
different kinds of information from the constraints
</UL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 17.1: Motivation</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial122.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial124.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
